package LeetCode算法;

import java.util.HashMap;
import java.util.concurrent.TimeoutException;

public class 数组元素求和索引 {

    public static void main(String[] args) {
        int[] array = {2, 7, 11, 15};
        int target = 9;
        for (int i:getSum1(array, target)){
            System.out.println(i);
        }
    }
    /**
     * 题目要求：给出一个数组和目标值，找出这个数组两个元素加起来的和等于目标值的索引
     * @param array：数组
     * @param target：目标值
     */
    public static int[] getSum1(int[] array,int target){
        //有两种方法，首先使用双层for循环，比较暴力但便于理解，时间复杂度为O(n²)，空间复杂度为O(1)
        long start = System.currentTimeMillis();
        int[] ans = new int[2];//创建结果数组
        for (int i=0;i<array.length;i++){//暴力破解直接上多层for循环
            for (int j=(i+1);j<array.length;j++){
                if (array[i]+array[j]==target){//这里array[i]+array[j]==target实际上可以看成sum[j]==target-sum[i]
                    ans[0]=i;
                    ans[1]=j;
                    long end = System.currentTimeMillis();
                    System.out.printf("总共耗时%d\r\n",end-start);
                    return ans;
                }
            }
        }
        return ans;
    }

    /**
     * 双层for中的if思想是对比两个索引下不同元素的和是否相同，相同则直接返回结果
     * 但实际上还有其他思路，就是目标值减去其中一个索引i的元素得到差值sub，也就是在数组可以找到两个元素的话这个sub一定等于另一个数组的元素索引j
     * 现在就顺着这个sub进行思考，可不可以只对比sub而不需要进行双层for循环
     *使用map结构存储数据，key为数组的元素，value为数组元素的索引
     * 写的思路则是先将数组的元素以及索引写入map，在一层for中寻找挨个求出每个元素与target的sub
     * 只要这个数组的任意两个元素加起来等于target，那么数组元素肯定存在与sub相同的情况
     * 因为map我们使用元素作为key，所以我们只需找sub是否存在与map中，存在的话还得先判断当前索引是否与map中的value的索引是否相等
     * 相等则表示读取到了同一个数
     * @param array
     * @param target
     * @return
     * @throws IllegalAccessException
     * 此步骤的时间复杂度为O(n)空间复杂度为O(n)
     */
    public static int[] getSum2(int[] array,int target) throws Exception {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i=0;i<array.length;i++){
            map.put(array[i],i);
        }
        for (int i=0;i<array.length;i++){
            int sub = target - array[i];
            if (map.containsKey(sub)&&map.get(sub)!=i){
                return new int[]{i,map.get(sub)};
            }
        }
        throw new TimeoutException("No two sum solution");
    }
}
